home *** CD-ROM | disk | FTP | other *** search
/ Graphics Plus / Graphics Plus.iso / media / objects / converte / 3dspv2 / rayopt.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-05-16  |  40.8 KB  |  1,733 lines
  1. /*-------------------------------------------------------------------------
  2.  
  3.            Bounding Shape Optimizer for PoV
  4.             Copyright (c) 1992 Steve Anger
  5.  
  6.     A number of C routines that can be used to generate PoV ray tracer
  7.  files from triangle data.  Supports generation of smooth triangles and an
  8.  optimal set of bounding shapes for much faster traces.  Output files are
  9.  compatible with PoV v0.5x.  This program may be freely modified and
  10.  distributed.
  11.                                            CompuServe: 70714,3113
  12.                                              Internet: steve.anger@rose.uucp
  13.                               You Can Call me Ray BBS: (708)358-5611
  14.  
  15. --------------------------------------------------------------------------*/
  16.  
  17.  
  18.  
  19. #ifndef _GNUC_
  20. #include <malloc.h>
  21. #else
  22. #include <std.h>
  23. #endif
  24.  
  25. #include <stdio.h>
  26. #include <stdlib.h>
  27. #include <string.h>
  28. #include <ctype.h>
  29. #include <math.h>
  30. #include "rayopt.h"
  31.  
  32. #define HASHSIZE  500           /* Size of hash table for vertex lookup */
  33. #define DEGEN_TOL (1e-8)        /* float comparison tolerance for checking
  34.                    for degenerate triangles */
  35. #define MAX_PAL   110           /* Maximum allowable number of texture
  36.                    declarations (PoV chokes around 120) */
  37. #ifndef PI
  38. #define PI 3.1415926536
  39. #endif
  40.  
  41. #ifndef MAXFLOAT
  42. #define MAXFLOAT (1e30)
  43. #endif
  44.  
  45. typedef struct {
  46.     float red;
  47.     float green;
  48.     float blue;
  49. } Palette;
  50.  
  51. typedef char *Texture;
  52.  
  53. typedef float Vector[3];
  54.  
  55. typedef struct {
  56.     unsigned vert[3];
  57.     unsigned text_index;
  58.     char     text_type;
  59.     char     flag;
  60. } Triangle;
  61.  
  62.  
  63. /* Linked list of triangles */
  64. typedef struct TList {
  65.     Triangle     *tri;
  66.     struct TList *next;
  67. } TriList;
  68.  
  69.  
  70. /* Double linked list of triangles */
  71. typedef struct TList2 {
  72.     Triangle      *tri;
  73.     struct TList2 *prev;
  74.     struct TList2 *next;
  75. } TriList2;
  76.  
  77.  
  78. /* List of triangle vertices */
  79. typedef struct VList {
  80.     unsigned     vert;
  81.     struct VList *next;
  82. } VertList;
  83.  
  84.  
  85. /* List of triangle groups */
  86. typedef struct GTree {
  87.     TriList2     *index[3];    /* Triangles indexed by x, y, and z coord */
  88.     Vector       vmin;         /* min/max extents of triangle vertices */
  89.     Vector       vmax;         /*    "       "     "     "        "     */
  90.     float        area;         /* Total surface area of bounding region */
  91.     unsigned     obj_cnt;      /* Total number of triangles in group */
  92.     int          child_cnt;    /* Number of children */
  93.     int          split_cnt;    /* Number of times this node has been split */
  94.     struct GTree *parent;      /* Parent of this node */
  95.     struct GTree *next;        /* Next node at this level */
  96.     struct GTree *child;       /* First child of this ndoe */
  97. } GroupTree;
  98.  
  99. Palette   *ptable;         /* Palette table */
  100. unsigned  pmax;            /* Maximum size of table */
  101. unsigned  psize;           /* Current size */
  102.  
  103. Texture   *ttable;         /* Named texture table */
  104. unsigned  tmax;            /* Maximum size of table */
  105. unsigned  tsize;           /* Current size */
  106.  
  107. Vector    *vtable;         /* Vertice table */
  108. unsigned  vmax;            /* Maximum size of table */
  109. unsigned  vsize;           /* Current size */
  110.  
  111. Vector    gmin = {+MAXFLOAT, +MAXFLOAT, +MAXFLOAT};
  112. Vector    gmax = {-MAXFLOAT, -MAXFLOAT, -MAXFLOAT};
  113.  
  114. VertList  *vert_hash[HASHSIZE];  /* Hash table for looking up vertices */
  115. TriList   **tri_index;           /* Index for smooth triangle generation */
  116.  
  117. GroupTree *groot;           /* Tree representing the object hierarchy */
  118.  
  119. int       initialized  = 0;
  120. int       quiet_mode   = 0;
  121. int       bound_mode   = 0;
  122. float     smooth_angle = 0.0;
  123. unsigned  vert_init    = 0;
  124. int       dec_point    = 4;
  125.  
  126. char      dat_file[64] = "rayopt.dat";
  127. char      inc_file[64] = "rayopt.inc";
  128.  
  129. unsigned  tot_bounds   = 0;
  130. unsigned  object_cnt   = 0;
  131.  
  132. Vector    last_vmin = {0.0, 0.0, 0.0};
  133. Vector    last_vmax = {0.0, 0.0, 0.0};
  134. unsigned  last_vert_cnt = 0;
  135. unsigned  last_tri_cnt = 0;
  136. float     last_index = 0.0;
  137. unsigned  last_bounds = 0;
  138.  
  139. Palette   last_pal;
  140. char      last_texture[64] = "";
  141. unsigned  texture_index;
  142. char      texture_type;
  143. char      object_name[64] = "";
  144.  
  145. float     orig_tpr;        /* Number of Tests Per Ray before optimization */
  146. float     final_tpr;       /*    "   "    "    "   "  after optimization */
  147. float     bound_cost;      /* Cost of testing a bound relative to testing */
  148.                /* a triangle */
  149.  
  150. /* Function prototypes */
  151. void init_object (void);
  152. void cleanup_object (void);
  153. float calc_tpr (GroupTree *gnode);
  154. GroupTree *create_group (void);
  155. void delete_tree (GroupTree *gnode);
  156. void optimize_tree (GroupTree *gnode);
  157. void test_split (GroupTree *gnode, int axis, float *best_rtpr, TriList2 **
  158.     best_loc);
  159. void split_group (GroupTree *gnode, int axis, TriList2 *split_loc, GroupTree *
  160.     *group_a, GroupTree **group_b);
  161. void write_pov(void);
  162. void write_tree (FILE *f, GroupTree *gnode, int level);
  163. void write_texture (FILE *f, Triangle *tri);
  164. void write_header (FILE *f);
  165. void write_triangle (FILE *f, Triangle *tri, int one_texture);
  166. void write_bound (FILE *f, GroupTree *gnode);
  167. void update_node (GroupTree *gnode);
  168. void sort_indexes (GroupTree *gnode);
  169. void quick_sort (TriList2 *start, TriList2 *end, int axis);
  170. void bound_shape (GroupTree *gnode, Vector bcenter, Vector bsize);
  171. float calc_radius (GroupTree *gnode, Vector bcenter, Vector dim);
  172. float surf_area (float a, float b, float c);
  173. float max_vertex (Triangle *tri, int axis);
  174. float min_vertex (Triangle *tri, int axis);
  175. float avg_vertex (Triangle *tri, int axis);
  176. void build_tri_index (void);
  177. void dump_tri_index (void);
  178. void vert_normal (Triangle *t, Vector *norm);
  179. void tri_normal (Triangle *t, Vector normal);
  180. unsigned pal_lookup (float red, float green, float blue);
  181. unsigned texture_lookup (char *texture_name);
  182. unsigned vert_lookup (float x, float y, float z);
  183. void vect_init (Vector v, float x, float y, float z);
  184. void vect_copy (Vector v1, Vector v2);
  185. int vect_equal (Vector v1, Vector v2);
  186. void vect_add (Vector v1, Vector v2, Vector v3);
  187. void vect_subtr (Vector v1, Vector v2, Vector v3);
  188. void vect_scale (Vector v, float k);
  189. float vect_mag (Vector v);
  190. float dot_prod (Vector v1, Vector v2);
  191. void cross_prod (Vector v1, Vector v2, Vector v3);
  192. float vect_angle (Vector v1, Vector v2);
  193. void vect_print (FILE *f, Vector v, int dec);
  194. int  degen_tri (float ax, float ay, float az, float bx, float by, float bz,
  195.      float cx, float cy, float cz);
  196. void abortmsg (char *msg, int exit_code);
  197. float fmin (float a, float b);
  198. float fmax (float a, float b);
  199.  
  200.  
  201. void opt_set_fname (char *dat_name, char *inc_name)
  202. {
  203.     FILE *f;
  204.  
  205.     strcpy (dat_file, dat_name);
  206.  
  207.     if (strlen(inc_name) > 0)
  208.     strcpy (inc_file, inc_name);
  209.     else {
  210.     strcpy (inc_file, dat_file);
  211.     add_ext (inc_file, "inc", 1);
  212.     }
  213.  
  214.     f = fopen (dat_file, "w");
  215.     fclose (f);
  216.  
  217.     f = fopen (inc_file, "w");
  218.     fclose (f);
  219. }
  220.  
  221.  
  222. void opt_set_quiet (int quiet)
  223. {
  224.     if (quiet != 0 && quiet != 1)
  225.     abortmsg ("ERROR: Invalid parameter passed to opt_set_quiet.", 1);
  226.  
  227.     quiet_mode = quiet;
  228. }
  229.  
  230.  
  231. void opt_set_bound (int bound)
  232. {
  233.     if (bound != 0 && bound != 1 && bound != 2)
  234.     abortmsg ("ERROR: Invalid parameter passed to opt_set_bound.", 1);
  235.  
  236.     bound_mode = bound;
  237. }
  238.  
  239.  
  240. void opt_set_smooth (float smooth)
  241. {
  242.     if (smooth < 0.0 || smooth > 180.0)
  243.     abortmsg ("ERROR: Invalid parameter passed to opt_set_smooth.", 1);
  244.  
  245.     smooth_angle = smooth;
  246. }
  247.  
  248.  
  249. void opt_set_vert (unsigned vert)
  250. {
  251.     vert_init = vert;
  252. }
  253.  
  254.  
  255. void opt_set_dec (int dec)
  256. {
  257.     if (dec < 0 || dec > 9)
  258.     abortmsg ("ERROR: Invalid parameter passed to opt_set_dec.", 1);
  259.  
  260.     dec_point = dec;
  261. }
  262.  
  263.  
  264. void opt_set_color (float red, float green, float blue)
  265. {
  266.     if (!initialized)
  267.     init_object();
  268.  
  269.     if (last_pal.red != red || last_pal.green != green ||
  270.                    last_pal.blue != blue || psize == 0) {
  271.     last_pal.red   = red;
  272.     last_pal.green = green;
  273.     last_pal.blue  = blue;
  274.  
  275.     texture_index = pal_lookup (red, green, blue);
  276.     }
  277.  
  278.     texture_type = 0;   /* An RGB texture */
  279. }
  280.  
  281.  
  282. void opt_set_texture (char *texture_name)
  283. {
  284.     char new_texture[64];
  285.     int i;
  286.  
  287.     if (!initialized)
  288.     init_object();
  289.  
  290.     if (!isdigit(texture_name[0]))
  291.     strcpy (new_texture, texture_name);
  292.     else {
  293.     /* Prepend an underscore to textures that begin with a number */
  294.     new_texture[0] = '_';
  295.     strcpy (&new_texture[1], texture_name);
  296.     }
  297.  
  298.     /* Replace any illegal characters in the name with underscores */
  299.     for (i = 0; new_texture[i] != '\0'; i++) {
  300.     if (!isalnum(new_texture[i]))
  301.         new_texture[i] = '_';
  302.     }
  303.  
  304.     if (strcmp (last_texture, new_texture) != 0) {
  305.     strcpy (last_texture, new_texture);
  306.     texture_index = texture_lookup (new_texture);
  307.     }
  308.  
  309.     texture_type = 1;   /* A named texture */
  310. }
  311.  
  312.  
  313. /* Add a new triangle to the database */
  314. int opt_add_tri (float ax, float ay, float az,
  315.          float bx, float by, float bz,
  316.          float cx, float cy, float cz)
  317. {
  318.     TriList2 *new_node;
  319.     Triangle *new_tri;
  320.     int      i;
  321.  
  322.     /* Check if the triangle is degenerate (zero area), if so return -1 */
  323.     if (degen_tri (ax, ay, az, bx, by, bz, cx, cy, cz))
  324.     return -1;
  325.  
  326.     if (!initialized)
  327.     init_object();
  328.  
  329.     /* Allocate memory for the new triangle */
  330.     new_tri = malloc (sizeof(Triangle));
  331.     if (new_tri == NULL)
  332.     abortmsg ("Insufficient memory for new triangles.", 1);
  333.  
  334.     /* Look up the vertex and texture indexes */
  335.     new_tri->vert[0] = vert_lookup (ax, ay, az);
  336.     new_tri->vert[1] = vert_lookup (bx, by, bz);
  337.     new_tri->vert[2] = vert_lookup (cx, cy, cz);
  338.  
  339.     new_tri->text_index = texture_index;
  340.     new_tri->text_type  = texture_type;
  341.  
  342.     new_tri->flag = 0;
  343.  
  344.     for (i = 0; i < 3; i++) {
  345.     /* Create a new index node */
  346.     new_node = malloc (sizeof(TriList2));
  347.     if (new_node == NULL)
  348.         abortmsg ("Insufficient memory for triangles.", 1);
  349.  
  350.     /* Point the index entry to the new triangle */
  351.     new_node->tri = new_tri;
  352.  
  353.     /* Insert the new index node into the list */
  354.     new_node->next = groot->index[i];
  355.     new_node->prev = groot->index[i]->prev;
  356.     groot->index[i]->prev->next = new_node;
  357.     groot->index[i]->prev = new_node;
  358.     }
  359.  
  360.     ++(groot->obj_cnt);
  361.  
  362.     return 0;
  363. }
  364.  
  365.  
  366. /* Optimize and write PoV file */
  367. void opt_write_pov (char *obj_name)
  368. {
  369.     VertList *temp;
  370.     int      i;
  371.  
  372.     if (!initialized || groot->obj_cnt == 0) {
  373.     orig_tpr = 1.0;
  374.     final_tpr = 0.0;
  375.     tot_bounds = 0;
  376.     return;   /* No triangles where ever added, nothing to write */
  377.     }
  378.  
  379.     strcpy (object_name, obj_name);
  380.     cleanup_name (object_name);
  381.  
  382.     ++object_cnt;
  383.  
  384.     /* Dump the hash table, don't need it any more */
  385.     for (i = 0; i < HASHSIZE; i++) {
  386.     while (vert_hash[i] != NULL) {
  387.         temp = vert_hash[i];
  388.         vert_hash[i] = vert_hash[i]->next;
  389.         free (temp);
  390.     }
  391.     }
  392.  
  393.     /* Build the vertice index */
  394.     if (smooth_angle > 0.0)
  395.     build_tri_index();
  396.  
  397.     if (bound_mode != 2) {
  398.     if (!quiet_mode)
  399.         printf ("Building indexes\n");
  400.  
  401.     sort_indexes (groot);
  402.     }
  403.  
  404.     update_node (groot);
  405.  
  406.     if (!quiet_mode) {
  407.     printf ("Adding bounds (1)\r");
  408.     fflush(stdout);;
  409.     }
  410.  
  411.     /* Optimize the tree */
  412.     orig_tpr = calc_tpr (groot);
  413.  
  414.     if (bound_mode != 2)
  415.     optimize_tree (groot);
  416.  
  417.     final_tpr = calc_tpr (groot);
  418.  
  419.     /* Write the file */
  420.     write_pov();
  421.  
  422.     /* Free up the vertex index */
  423.     if (smooth_angle > 0.0)
  424.     dump_tri_index();
  425.  
  426.     cleanup_object();
  427. }
  428.  
  429.  
  430. /* Adds the INCLUDE line to the output file */
  431. void opt_finish()
  432. {
  433.     FILE *f;
  434.  
  435.     if (strcmp (dat_file, inc_file) != 0) {
  436.     f = fopen (dat_file, "a");
  437.     if (f == NULL)
  438.         abortmsg ("Error opening output file.", 1);
  439.  
  440.     fprintf (f, "#include \"%s\"\n", inc_file);
  441.  
  442.     fclose(f);
  443.     }
  444. }
  445.  
  446.  
  447.  
  448. void opt_get_limits (float *min_x, float *min_y, float *min_z,
  449.              float *max_x, float *max_y, float *max_z)
  450. {
  451.     *min_x = last_vmin[0];
  452.     *min_y = last_vmin[1];
  453.     *min_z = last_vmin[2];
  454.  
  455.     *max_x = last_vmax[0];
  456.     *max_y = last_vmax[1];
  457.     *max_z = last_vmax[2];
  458. }
  459.  
  460.  
  461. void opt_get_glimits (float *min_x, float *min_y, float *min_z,
  462.               float *max_x, float *max_y, float *max_z)
  463. {
  464.     *min_x = gmin[0];
  465.     *min_y = gmin[1];
  466.     *min_z = gmin[2];
  467.  
  468.     *max_x = gmax[0];
  469.     *max_y = gmax[1];
  470.     *max_z = gmax[2];
  471. }
  472.  
  473.  
  474. unsigned opt_get_vert_cnt()
  475. {
  476.     return last_vert_cnt;
  477. }
  478.  
  479.  
  480. unsigned opt_get_tri_cnt()
  481. {
  482.     return last_tri_cnt;
  483. }
  484.  
  485.  
  486. float opt_get_index()
  487. {
  488.     return last_index;
  489. }
  490.  
  491.  
  492. unsigned opt_get_bounds()
  493. {
  494.     return last_bounds;
  495. }
  496.  
  497.  
  498. void init_object()
  499. {
  500.     int i;
  501.  
  502.     last_pal.red   = 0.0;
  503.     last_pal.green = 0.0;
  504.     last_pal.blue  = 0.0;
  505.  
  506.     strcpy (last_texture, "");
  507.  
  508.     if (bound_mode == 0)
  509.     bound_cost = 1.6;
  510.     else
  511.     bound_cost = 3.6;
  512.  
  513.     /* Allocate memory for palette lookup table */
  514.     pmax   = 10;
  515.     psize  = 0;
  516.     ptable = malloc (pmax * sizeof(Palette));
  517.     if (ptable == NULL)
  518.     abortmsg ("Insufficient memory for palette.", 1);
  519.  
  520.     /* Allocate memory for texture table */
  521.     tmax   = 10;
  522.     tsize  = 0;
  523.     ttable = malloc (tmax * sizeof(Texture));
  524.     if (ttable == NULL)
  525.     abortmsg ("Insufficient memory for textures.", 1);
  526.  
  527.     /* Allocate memory for vertex lookup table */
  528.     vmax = (vert_init > 0) ? vert_init : 1000;
  529.     vsize  = 0;
  530.     vtable = malloc (vmax * sizeof(Vector));
  531.     if (vtable == NULL)
  532.     abortmsg ("Insufficient memory for vertices.", 1);
  533.  
  534.     /* Initialize the vertex lookup hash table */
  535.     for (i = 0; i < HASHSIZE; i++)
  536.     vert_hash[i] = NULL;
  537.  
  538.     /* Start with an empty root node */
  539.     groot = create_group();
  540.  
  541.     tot_bounds = 1;
  542.     initialized = 1;
  543. }
  544.  
  545.  
  546. void cleanup_object()
  547. {
  548.     int i;
  549.  
  550.     last_vert_cnt = vsize;
  551.     last_tri_cnt  = groot->obj_cnt;
  552.     last_index    = orig_tpr/final_tpr;
  553.     last_bounds   = tot_bounds;
  554.  
  555.     vect_copy (last_vmin, groot->vmin);
  556.     vect_copy (last_vmax, groot->vmax);
  557.  
  558.     gmin[0] = (last_vmin[0] < gmin[0]) ? last_vmin[0] : gmin[0];
  559.     gmin[1] = (last_vmin[1] < gmin[1]) ? last_vmin[1] : gmin[1];
  560.     gmin[2] = (last_vmin[2] < gmin[2]) ? last_vmin[2] : gmin[2];
  561.  
  562.     gmax[0] = (last_vmax[0] > gmax[0]) ? last_vmax[0] : gmax[0];
  563.     gmax[1] = (last_vmax[1] > gmax[1]) ? last_vmax[1] : gmax[1];
  564.     gmax[2] = (last_vmax[2] > gmax[2]) ? last_vmax[2] : gmax[2];
  565.  
  566.     free (ptable);
  567.     free (vtable);
  568.  
  569.     for (i = 0; i < tsize; i++)
  570.     free (ttable[i]);
  571.  
  572.     free (ttable);
  573.  
  574.     delete_tree (groot);
  575.  
  576.     initialized = 0;
  577. }
  578.  
  579.  
  580. /* Calculate the number of Tests Per Ray (tpr) required for this group */
  581. float calc_tpr (GroupTree *gnode)
  582. {
  583.     GroupTree *g;
  584.     float tpr;
  585.  
  586.     if (gnode->child_cnt == 0)
  587.     return gnode->obj_cnt;
  588.  
  589.     tpr = bound_cost * gnode->child_cnt;
  590.  
  591.     for (g = gnode->child; g != NULL; g = g->next)
  592.     tpr = tpr + (g->area/gnode->area) * calc_tpr(g);
  593.  
  594.     return tpr;
  595. }
  596.  
  597.  
  598. /* Create an empty group node */
  599. GroupTree *create_group()
  600. {
  601.     GroupTree *new_group;
  602.     int       i;
  603.  
  604.     new_group = malloc (sizeof(GroupTree));
  605.     if (new_group == NULL)
  606.     abortmsg ("Insufficient memory for group list.", 1);
  607.  
  608.     for (i = 0; i < 3; i++) {
  609.     new_group->index[i] = malloc (sizeof(TriList2));
  610.     if (new_group->index[i] == NULL)
  611.         abortmsg ("Insufficient memory for tree.", 1);
  612.  
  613.     new_group->index[i]->tri = NULL;
  614.     new_group->index[i]->prev = new_group->index[i];
  615.     new_group->index[i]->next = new_group->index[i];
  616.     }
  617.  
  618.     vect_init (new_group->vmin, +MAXFLOAT, +MAXFLOAT, +MAXFLOAT);
  619.     vect_init (new_group->vmax, -MAXFLOAT, -MAXFLOAT, -MAXFLOAT);
  620.     new_group->area      = 0.0;
  621.     new_group->obj_cnt   = 0;
  622.     new_group->child_cnt = 0;
  623.     new_group->split_cnt = 0;
  624.     new_group->parent    = NULL;
  625.     new_group->next      = NULL;
  626.     new_group->child     = NULL;
  627.  
  628.     return new_group;
  629. }
  630.  
  631.  
  632. /* Delete this node and all sub-nodes of tree */
  633. void delete_tree (GroupTree *gnode)
  634. {
  635.     GroupTree *g, *g_temp;
  636.     TriList2  *t, *t_temp;
  637.     int       i;
  638.  
  639.     for (g = gnode->child; g != NULL; ) {
  640.     g_temp = g->next;
  641.     delete_tree (g);
  642.     g = g_temp;
  643.     }
  644.  
  645.     /* Free the indexes for this node (if any exist) */
  646.     for (i = 0; i < 3; i++) {
  647.     if ((gnode->index[i] != NULL) && (gnode->index[i]->prev != NULL)) {
  648.         /* Drop a link so the list isn't circular any more */
  649.         gnode->index[i]->prev->next = NULL;
  650.  
  651.         /* Delete the list */
  652.         for (t = gnode->index[i]; t != NULL; ) {
  653.         if (i == 0 && (t->tri != NULL))
  654.             free (t->tri);
  655.  
  656.         t_temp = t;
  657.         t = t->next;
  658.         free (t_temp);
  659.         }
  660.     }
  661.     }
  662.  
  663.     /* And finally free the root node */
  664.     free (gnode);
  665. }
  666.  
  667.  
  668. /* Optimize the bounds for this sub-tree */
  669. void optimize_tree (GroupTree *gnode)
  670. {
  671.     GroupTree *group_a, *group_b;
  672.     int axis, best_axis;
  673.     float     best_rtpr, new_rtpr;
  674.     TriList2  *best_loc, *new_loc;
  675.  
  676.     best_rtpr = 0.0;
  677.     best_loc  = NULL;
  678.     best_axis = -1;
  679.  
  680.     /* Try splitting the group in each of the three axis' (x,y,z) */
  681.     for (axis = 0; axis < 3; axis++) {
  682.     test_split (gnode, axis, &new_rtpr, &new_loc);
  683.  
  684.     if (new_rtpr < best_rtpr) {
  685.         best_rtpr = new_rtpr;
  686.         best_loc  = new_loc;
  687.         best_axis = axis;
  688.     }
  689.     }
  690.  
  691.     if (best_axis != -1) {
  692.     /* Split this node into two nodes */
  693.     split_group (gnode, best_axis, best_loc, &group_a, &group_b);
  694.  
  695.     optimize_tree (group_a);
  696.     optimize_tree (group_b);
  697.     }
  698. }
  699.  
  700.  
  701.  
  702. /* Test the effectiveness of splitting this group (but don't do it yet) */
  703. void test_split (GroupTree *gnode, int axis, float *best_rtpr,
  704.          TriList2 **best_loc)
  705. {
  706.     float    dim1, dim2;
  707.     float    area1, area2, p_area;
  708.     float    new_index, best_index;
  709.     float    new_min1, new_max1, new_min2, new_max2;
  710.     TriList2 *t;
  711.     int      cnt, best_cnt;
  712.  
  713.     *best_loc  = NULL;
  714.     best_index = +MAXFLOAT;
  715.     cnt = 0;
  716.  
  717.     dim1 = gnode->vmax[(axis+1) % 3] - gnode->vmin[(axis+1) % 3];
  718.     dim2 = gnode->vmax[(axis+2) % 3] - gnode->vmin[(axis+2) % 3];
  719.  
  720.     for (t = gnode->index[axis]->next; t != gnode->index[axis]; t = t->next) {
  721.     if (t->next == gnode->index[axis])
  722.         break;
  723.  
  724.     ++cnt;
  725.  
  726.     /* Make an estimate of the new min/max limits, doing the full */
  727.     /* calculation is just tooooo slooowww. */
  728.     new_min1 = gnode->vmin[axis];
  729.     new_max1 = max_vertex (t->tri, axis);
  730.     new_min2 = min_vertex (t->next->tri, axis);
  731.     new_max2 = gnode->vmax[axis];
  732.  
  733.     /* Calculate the surface area of the new groups */
  734.     area1 = surf_area (dim1, dim2, new_max1 - new_min1);
  735.     area2 = surf_area (dim1, dim2, new_max2 - new_min2);
  736.  
  737.     new_index = (cnt * area1) + ((gnode->obj_cnt - cnt) * area2);
  738.  
  739.     /* Keep track of the best one */
  740.     if (new_index < best_index) {
  741.         best_index = new_index;
  742.         *best_loc  = t->next;
  743.         best_cnt   = cnt;
  744.     }
  745.     }
  746.  
  747.     /* The former was just an estimate, verify the numbers */
  748.     if (*best_loc != NULL) {
  749.     new_min1 = gnode->vmin[axis];
  750.     new_max1 = -MAXFLOAT;
  751.     new_min2 = +MAXFLOAT;
  752.     new_max2 = gnode->vmax[axis];
  753.  
  754.     for (t = gnode->index[axis]->next; t != *best_loc; t = t->next)
  755.         new_max1 = fmax (new_max1, max_vertex (t->tri, axis));
  756.  
  757.     for (t = *best_loc; t != gnode->index[axis]; t = t->next)
  758.         new_min2 = fmin (new_min2, min_vertex (t->tri, axis));
  759.  
  760.     area1 = surf_area (dim1, dim2, new_max1 - new_min1);
  761.     area2 = surf_area (dim1, dim2, new_max2 - new_min2);
  762.  
  763.     best_index = (best_cnt * area1) +
  764.              ((gnode->obj_cnt - best_cnt) * area2);
  765.     }
  766.  
  767.     if (gnode->parent == NULL || gnode->split_cnt >= 2) {
  768.     p_area = gnode->area;
  769.  
  770.     *best_rtpr = -1.0*((gnode->area/p_area) * gnode->obj_cnt) +
  771.              (gnode->area/p_area) * ((best_index/gnode->area) +
  772.              2.0*bound_cost);
  773.     }
  774.     else {
  775.     p_area = gnode->parent->area;
  776.  
  777.     *best_rtpr = -1.0*((gnode->area/p_area) * gnode->obj_cnt) +
  778.              (best_index/p_area) + bound_cost;
  779.     }
  780. }
  781.  
  782.  
  783. /* Split the group along the specified axis into two sub-groups */
  784. void split_group (GroupTree *gnode, int axis, TriList2 *split_loc,
  785.           GroupTree **group_a, GroupTree **group_b)
  786. {
  787.     GroupTree *new_a, *new_b;
  788.     TriList2  *t, *next_t, *new_index;
  789.     char      new_flag;
  790.     int       i;
  791.  
  792.     /* Mark the triangles as to which group they will belong */
  793.     new_flag = 0;
  794.     for (t = gnode->index[axis]->next; t != gnode->index[axis]; t = t->next) {
  795.     if (t == split_loc)
  796.         new_flag = 1;
  797.  
  798.     t->tri->flag = new_flag;
  799.     }
  800.  
  801.     new_a = create_group();
  802.     new_b = create_group();
  803.  
  804.     for (i = 0; i < 3; i++) {
  805.     for (t = gnode->index[i]->next; t != gnode->index[i]; t = next_t) {
  806.         next_t = t->next;
  807.  
  808.         if (t->tri->flag == 0)
  809.         new_index = new_a->index[i];
  810.         else
  811.         new_index = new_b->index[i];
  812.  
  813.         /* Remove this node from the list */
  814.         t->prev->next = t->next;
  815.         t->next->prev = t->prev;
  816.  
  817.         /* Insert node into its new group */
  818.         t->prev = new_index->prev;
  819.         t->next = new_index;
  820.         new_index->prev->next = t;
  821.         new_index->prev = t;
  822.     }
  823.     }
  824.  
  825.     for (i = 0; i < 3; i++) {
  826.     free (gnode->index[i]);
  827.     gnode->index[i] = NULL;
  828.     }
  829.  
  830.     if (gnode->parent == NULL || gnode->split_cnt >= 2) {
  831.     /* Add the new groups as children of original */
  832.     gnode->child  = new_a;
  833.     new_a->parent = gnode;
  834.     new_a->next   = new_b;
  835.     new_b->parent = gnode;
  836.  
  837.     new_a->split_cnt = 0;
  838.     new_b->split_cnt = 0;
  839.  
  840.     tot_bounds = tot_bounds + 2;
  841.     }
  842.     else {
  843.     /* Remove the original group and replace with the new groups */
  844.     for (i = 0; i < 3; i++)
  845.         gnode->index[i] = new_a->index[i];
  846.  
  847.     free (new_a);
  848.     new_a = gnode;
  849.  
  850.     new_b->next = new_a->next;
  851.     new_a->next = new_b;
  852.  
  853.     new_a->parent = gnode->parent;
  854.     new_b->parent = gnode->parent;
  855.  
  856.     new_a->split_cnt = gnode->split_cnt + 1;
  857.     new_b->split_cnt = gnode->split_cnt + 1;
  858.  
  859.     tot_bounds = tot_bounds + 1;
  860.     }
  861.  
  862.     update_node (new_a);
  863.     update_node (new_b);
  864.  
  865.     if (new_a->parent != NULL)
  866.     update_node (new_a->parent);
  867.  
  868.     if (!quiet_mode) {
  869.     printf ("Adding bounds (%d)\r", tot_bounds);
  870.     fflush(stdout);
  871.     }
  872.  
  873.     *group_a = new_a;
  874.     *group_b = new_b;
  875. }
  876.  
  877.  
  878. /* Write the optimized PoV file */
  879. void write_pov()
  880. {
  881.     FILE  *f;
  882.  
  883.     if (!quiet_mode)
  884.     printf ("\nWriting files %s and %s\n", dat_file, inc_file);
  885.  
  886.     f = fopen (dat_file, "a");
  887.     if (f == NULL)
  888.     abortmsg ("Error opening output file.", 1);
  889.  
  890.     write_header (f);
  891.  
  892.     fclose (f);
  893.  
  894.     f = fopen (inc_file, "a");
  895.     if (f == NULL)
  896.     abortmsg ("Error opening output file.", 1);
  897.  
  898.     write_tree (f, groot, 1);
  899.  
  900.     fclose (f);
  901.  
  902.     if (!quiet_mode) {
  903.     printf ("Triangles: %u, ", groot->obj_cnt);
  904.     printf ("vertices: %u, ", vsize);
  905.     printf ("Bounding index: %.2f\n\n", orig_tpr/final_tpr);
  906.     }
  907. }
  908.  
  909.  
  910. /* Write a sub-tree to file */
  911. void write_tree (FILE *f, GroupTree *gnode, int level)
  912. {
  913.     GroupTree *g;
  914.     TriList2  *t;
  915.     Triangle  *first_tri;
  916.     int       one_texture;
  917.  
  918.     if (level == 1)
  919.     fprintf (f, "\n/* Object '%s' */\n", object_name);
  920.  
  921.     fprintf (f, "composite\n");
  922.  
  923.     if (gnode->child != NULL) {
  924.     for (g = gnode->child; g != NULL; g = g->next)
  925.         write_tree (f, g, level+1);
  926.     }
  927.     else {
  928.     first_tri = gnode->index[0]->next->tri;
  929.     one_texture = 1;
  930.  
  931.     for (t = gnode->index[0]->next; t != gnode->index[0]; t = t->next) {
  932.         if (t->tri->text_index != first_tri->text_index ||
  933.         t->tri->text_type  != first_tri->text_type) {
  934.            one_texture = 0;
  935.            break;
  936.         }
  937.     }
  938.  
  939.     if (one_texture) {
  940.         fprintf (f, "\tobject\n");
  941.         fprintf (f, "\t\tunion\n");
  942.     }
  943.  
  944.     for (t = gnode->index[0]->next; t != gnode->index[0]; t = t->next)
  945.         write_triangle (f, t->tri, one_texture);
  946.  
  947.     if (one_texture) {
  948.         fprintf (f, "\t\tend_union\n\n\t\t");
  949.         write_texture (f, first_tri);
  950.         fprintf (f, "\n\tend_object\n");
  951.     }
  952.     }
  953.  
  954.     write_bound (f, gnode);
  955.  
  956.     fprintf (f, "end_composite\n");
  957. }
  958.  
  959.  
  960. void write_texture (FILE *f, Triangle *tri)
  961. {
  962.     if (tri->text_type == 1)
  963.     fprintf (f, "texture %s end_texture", ttable[tri->text_index]);
  964.     else if (psize < MAX_PAL)
  965.     fprintf (f, "texture %s_C%u end_texture",
  966.          object_name, tri->text_index + 1);
  967.     else
  968.     fprintf (f, "texture DefTexture color red %.3f green %.3f blue %.3f end_texture",
  969.          ptable[tri->text_index].red, ptable[tri->text_index].green, ptable[tri->text_index].blue);
  970. }
  971.  
  972.  
  973. /* Write the PoV file header */
  974. void write_header (FILE *f)
  975. {
  976.     int i;
  977.  
  978.     if (object_cnt == 1) {
  979.     fprintf (f, "/* Ellipsoid used as bounding shape */\n");
  980.     fprintf (f, "declare Ellipsoid = quadric\n");
  981.     fprintf (f, "    <1 1 1>\n");
  982.     fprintf (f, "    <0 0 0>\n");
  983.     fprintf (f, "    <0 0 0>\n");
  984.     fprintf (f, "    -1\n");
  985.     fprintf (f, "end_quadric\n\n");
  986.  
  987.     fprintf (f, "/* Default texture for all objects */\n");
  988.     fprintf (f, "declare DefTexture = texture\n");
  989.     fprintf (f, "    ambient 0.2\n");
  990.     fprintf (f, "    diffuse 0.6\n");
  991.     fprintf (f, "    phong 1.0\n");
  992.     fprintf (f, "    phongsize 70.0\n");
  993.     fprintf (f, "end_texture\n\n");
  994.     }
  995.  
  996.     if (psize >= MAX_PAL)
  997.     fprintf (f, "/* Too many textures, textures generated in-line */\n\n");
  998.     else {
  999.     if (psize > 0)
  1000.         fprintf (f, "/* Texture declarations for object '%s' */\n", object_name);
  1001.  
  1002.     for (i = 0; i < psize; i++) {
  1003.         fprintf (f, "declare %s_C%u = texture\n", object_name, i + 1);
  1004.         fprintf (f, "    DefTexture\n");
  1005.         fprintf (f, "    color red %.3f green %.3f blue %.3f\n",
  1006.              ptable[i].red, ptable[i].green, ptable[i].blue);
  1007.         fprintf (f, "end_texture\n\n");
  1008.     }
  1009.     }
  1010. }
  1011.  
  1012.  
  1013. /* Write a triangle (smooth or regular) */
  1014. void write_triangle (FILE *f, Triangle *tri, int one_texture)
  1015. {
  1016.     Vector norm[3];
  1017.     int    no_smooth = 0;
  1018.  
  1019.     if (one_texture)
  1020.     fprintf (f, "\t\t");
  1021.     else
  1022.     fprintf (f, "\tobject ");
  1023.  
  1024.     if (smooth_angle > 0.0) {
  1025.     vert_normal (tri, norm);
  1026.  
  1027.     if (vect_equal (norm[0], norm[1]) && vect_equal (norm[1], norm[2]))
  1028.         no_smooth = 1;
  1029.     }
  1030.  
  1031.     if (smooth_angle > 0.0 && !no_smooth) {
  1032.     fprintf (f, "smooth_triangle ");
  1033.     vect_print (f, vtable[tri->vert[0]], dec_point);
  1034.     vect_print (f, norm[0], dec_point);
  1035.     vect_print (f, vtable[tri->vert[1]], dec_point);
  1036.     vect_print (f, norm[1], dec_point);
  1037.     vect_print (f, vtable[tri->vert[2]], dec_point);
  1038.     vect_print (f, norm[2], dec_point);
  1039.     fprintf (f, "end_triangle");
  1040.     }
  1041.     else {
  1042.     fprintf (f, "triangle ");
  1043.     vect_print (f, vtable[tri->vert[0]], dec_point);
  1044.     vect_print (f, vtable[tri->vert[1]], dec_point);
  1045.     vect_print (f, vtable[tri->vert[2]], dec_point);
  1046.     fprintf (f, "end_triangle");
  1047.     }
  1048.  
  1049.     if (!one_texture) {
  1050.     fprintf (f, " ");
  1051.     write_texture (f, tri);
  1052.     fprintf (f, " end_object");
  1053.     }
  1054.  
  1055.     fprintf (f, "\n");
  1056. }
  1057.  
  1058.  
  1059. /* Write a bounding shape */
  1060. void write_bound (FILE *f, GroupTree *gnode)
  1061. {
  1062.     Vector bcenter, bsize;
  1063.  
  1064.     if (bound_mode == 0) {
  1065.     /* Use an ellipsoid as bounding shape */
  1066.     bound_shape (gnode, bcenter, bsize);
  1067.  
  1068.     if (gnode->obj_cnt > 1) {
  1069.         fprintf (f, "\n\tbounded_by quadric\n");
  1070.         fprintf (f, "\t\tEllipsoid\n");
  1071.         fprintf (f, "\t\tscale ");
  1072.         vect_print (f, bsize, dec_point + 1);
  1073.         fprintf (f, "\n\t\ttranslate ");
  1074.         vect_print (f, bcenter, dec_point + 1);
  1075.         fprintf (f, "\n\tend_quadric end_bound\n");
  1076.     }
  1077.     }
  1078.     else {
  1079.     /* Use a box as bounding shape */
  1080.     if (gnode->obj_cnt > 1) {
  1081.         fprintf (f, "\n\tbounded_by intersection\n");
  1082.         fprintf (f, "\t\tplane <+1 0 0> %.2f end_plane\n", +gnode->vmax[0]);
  1083.         fprintf (f, "\t\tplane <-1 0 0> %.2f end_plane\n", -gnode->vmin[0]);
  1084.         fprintf (f, "\t\tplane <0 +1 0> %.2f end_plane\n", +gnode->vmax[1]);
  1085.         fprintf (f, "\t\tplane <0 -1 0> %.2f end_plane\n", -gnode->vmin[1]);
  1086.         fprintf (f, "\t\tplane <0 0 +1> %.2f end_plane\n", +gnode->vmax[2]);
  1087.         fprintf (f, "\t\tplane <0 0 -1> %.2f end_plane\n", -gnode->vmin[2]);
  1088.         fprintf (f, "\tend_intersection end_bound\n");
  1089.     }
  1090.     }
  1091. }
  1092.  
  1093.  
  1094. /* Update the stats (area, vmin/vmax, child_cnt, etc.) for this node */
  1095. void update_node (GroupTree *gnode)
  1096. {
  1097.     GroupTree *g;
  1098.     TriList2  *t;
  1099.     int       i;
  1100.  
  1101.     vect_init (gnode->vmin, +MAXFLOAT, +MAXFLOAT, +MAXFLOAT);
  1102.     vect_init (gnode->vmax, -MAXFLOAT, -MAXFLOAT, -MAXFLOAT);
  1103.  
  1104.     gnode->obj_cnt   = 0;
  1105.     gnode->child_cnt = 0;
  1106.  
  1107.     if (gnode->index[0] == NULL) {
  1108.     /* Not a leaf node, calc the info from the child nodes */
  1109.  
  1110.     for (g = gnode->child; g != NULL; g = g->next) {
  1111.         ++(gnode->child_cnt);
  1112.  
  1113.         gnode->obj_cnt += g->obj_cnt;
  1114.  
  1115.         for (i = 0; i < 3; i++) {
  1116.         gnode->vmin[i] = fmin (gnode->vmin[i], g->vmin[i]);
  1117.         gnode->vmax[i] = fmax (gnode->vmax[i], g->vmax[i]);
  1118.         }
  1119.     }
  1120.     }
  1121.     else {
  1122.     /* A leaf node, calc the info from the triangle list */
  1123.  
  1124.     for (t = gnode->index[0]->next; t != gnode->index[0]; t = t->next) {
  1125.         ++(gnode->obj_cnt);
  1126.  
  1127.         for (i = 0; i < 3; i++) {
  1128.         gnode->vmin[i] = fmin (gnode->vmin[i], min_vertex (t->tri, i));
  1129.         gnode->vmax[i] = fmax (gnode->vmax[i], max_vertex (t->tri, i));
  1130.         }
  1131.     }
  1132.     }
  1133.  
  1134.     /* Update total surface area of region */
  1135.     gnode->area = surf_area (gnode->vmax[0] - gnode->vmin[0],
  1136.                  gnode->vmax[1] - gnode->vmin[1],
  1137.                  gnode->vmax[2] - gnode->vmin[2]);
  1138. }
  1139.  
  1140.  
  1141. void sort_indexes (GroupTree *gnode)
  1142. {
  1143.     int i;
  1144.  
  1145.     for (i = 0; i < 3; i++)
  1146.     quick_sort (gnode->index[i]->next, gnode->index[i]->prev, i);
  1147. }
  1148.  
  1149.  
  1150. void quick_sort (TriList2 *start, TriList2 *end, int axis)
  1151. {
  1152.     TriList2 *a, *b;
  1153.     Triangle *temp;
  1154.     float middle;
  1155.  
  1156.     if (start == end)
  1157.     return;
  1158.  
  1159.     a = start;
  1160.     b = end;
  1161.     middle = avg_vertex (a->tri, axis);
  1162.  
  1163.     do {
  1164.     while (avg_vertex (b->tri, axis) >= middle && a != b)
  1165.         b = b->prev;
  1166.  
  1167.     if (a != b) {
  1168.         temp   = a->tri;
  1169.         a->tri = b->tri;
  1170.         b->tri = temp;
  1171.  
  1172.         while (avg_vertex (a->tri, axis) <= middle && a != b)
  1173.         a = a->next;
  1174.  
  1175.         if (a != b) {
  1176.         temp   = a->tri;
  1177.         a->tri = b->tri;
  1178.         b->tri = temp;
  1179.         }
  1180.     }
  1181.     } while (a != b);
  1182.  
  1183.     if (a != start)
  1184.     quick_sort (start, a->prev, axis);
  1185.  
  1186.     if (b != end)
  1187.     quick_sort (b->next, end, axis);
  1188. }
  1189.  
  1190.  
  1191. /* Find an ellipsoid that encloses all of the triangles */
  1192. void bound_shape (GroupTree *gnode, Vector bcenter, Vector bsize)
  1193. {
  1194.     Vector dim;
  1195.     float  max_radius;
  1196.  
  1197.     vect_add   (bcenter, gnode->vmax, gnode->vmin);
  1198.     vect_scale (bcenter, 0.5);
  1199.     vect_subtr (dim, gnode->vmax, gnode->vmin);
  1200.  
  1201.     max_radius = calc_radius (gnode, bcenter, dim);
  1202.  
  1203.     vect_copy (bsize, dim);
  1204.     vect_scale (bsize, max_radius);
  1205. }
  1206.  
  1207.  
  1208. float calc_radius (GroupTree *gnode, Vector bcenter, Vector dim)
  1209. {
  1210.     GroupTree *g;
  1211.     TriList2  *t;
  1212.     Vector    norm;
  1213.     int       vr, i;
  1214.     float     radius;
  1215.     float     max_radius;
  1216.  
  1217.     max_radius = 0.0;
  1218.  
  1219.     if (gnode->index[0] != NULL) {
  1220.     for (t = gnode->index[0]->next; t != gnode->index[0]; t = t->next) {
  1221.         for (vr = 0; vr < 3; vr++) {
  1222.         for (i = 0; i < 3; i++) {
  1223.             if (dim[i] == 0.0)
  1224.             dim[i] = 0.01;
  1225.  
  1226.             norm[i] = (vtable[t->tri->vert[vr]][i] - bcenter[i])/dim[i];
  1227.         }
  1228.  
  1229.         radius = vect_mag (norm);
  1230.         if (radius > max_radius)
  1231.             max_radius = radius;
  1232.         }
  1233.     }
  1234.     }
  1235.     else {
  1236.     for (g = gnode->child; g != NULL; g = g->next) {
  1237.         radius = calc_radius (g, bcenter, dim);
  1238.         if (radius > max_radius)
  1239.         max_radius = radius;
  1240.     }
  1241.     }
  1242.  
  1243.     return max_radius;
  1244. }
  1245.  
  1246.  
  1247. /* Calculate the surface area of a box */
  1248. float surf_area (float a, float b, float c)
  1249. {
  1250.     return 2.0*(a*b + b*c + c*a);
  1251. }
  1252.  
  1253.  
  1254. float max_vertex (Triangle *tri, int axis)
  1255. {
  1256.     float max_v, val;
  1257.     int i;
  1258.  
  1259.     max_v = -MAXFLOAT;
  1260.  
  1261.     for (i = 0; i < 3; i++) {
  1262.     val = vtable[tri->vert[i]][axis];
  1263.  
  1264.     if (val > max_v)
  1265.         max_v = val;
  1266.     }
  1267.  
  1268.     return max_v;
  1269. }
  1270.  
  1271.  
  1272. float min_vertex (Triangle *tri, int axis)
  1273. {
  1274.     float min_v, val;
  1275.     int i;
  1276.  
  1277.     min_v = +MAXFLOAT;
  1278.  
  1279.     for (i = 0; i < 3; i++) {
  1280.     val = vtable[tri->vert[i]][axis];
  1281.  
  1282.     if (val < min_v)
  1283.         min_v = val;
  1284.     }
  1285.  
  1286.     return min_v;
  1287. }
  1288.  
  1289.  
  1290. float avg_vertex (Triangle *tri, int axis)
  1291. {
  1292.     float avg;
  1293.  
  1294.     avg = (vtable[tri->vert[0]][axis] + vtable[tri->vert[1]][axis] +
  1295.        vtable[tri->vert[2]][axis])/3.0;
  1296.  
  1297.     return avg;
  1298. }
  1299.  
  1300.  
  1301. /* Build an index of which triangles touch each vertex.  Used to */
  1302. /* speed up smooth triangle normal calculations. */
  1303. void build_tri_index()
  1304. {
  1305.     GroupTree *g;
  1306.     TriList   *temp;
  1307.     TriList2  *t;
  1308.     unsigned  i, vert_no;
  1309.  
  1310.     if (vsize == 0)
  1311.     return;
  1312.  
  1313.     tri_index = malloc (vsize * sizeof(TriList));
  1314.     if (tri_index == NULL)
  1315.     abortmsg ("Insufficient memory for smooth triangles.", 1);
  1316.  
  1317.     for (i = 0; i < vsize; i++)
  1318.     tri_index[i] = NULL;
  1319.  
  1320.     for (g = groot; g != NULL; g = g->next) {
  1321.     for (t = g->index[0]->next; t != g->index[0]; t = t->next) {
  1322.         for (i = 0; i < 3; i++) {
  1323.         vert_no = t->tri->vert[i];
  1324.         temp = tri_index[vert_no];
  1325.         tri_index[vert_no] = malloc (sizeof(TriList));
  1326.         if (tri_index[vert_no] == NULL)
  1327.             abortmsg ("Insufficient memory for smooth triangles.\n", 1);
  1328.  
  1329.         tri_index[vert_no]->tri = t->tri;
  1330.         tri_index[vert_no]->next = temp;
  1331.         }
  1332.     }
  1333.     }
  1334.  
  1335. }
  1336.  
  1337.  
  1338. void dump_tri_index()
  1339. {
  1340.     TriList *temp;
  1341.     int     i;
  1342.  
  1343.     for (i = 0; i < vsize; i++) {
  1344.     while (tri_index[i] != NULL) {
  1345.         temp = tri_index[i];
  1346.         tri_index[i] = tri_index[i]->next;
  1347.         free (temp);
  1348.     }
  1349.     }
  1350.  
  1351.     free (tri_index);
  1352. }
  1353.  
  1354.  
  1355. /* Calculates the smooth triangle normal for this vertex */
  1356. void vert_normal (Triangle *t, Vector *norm)
  1357. {
  1358.     Vector  curr_norm, new_norm;
  1359.     TriList *p;
  1360.     float   mag;
  1361.     int     i;
  1362.  
  1363.     tri_normal (t, curr_norm);
  1364.  
  1365.     for (i = 0; i < 3; i++) {
  1366.     vect_init (norm[i], 0.0, 0.0, 0.0);
  1367.  
  1368.     for (p = tri_index[t->vert[i]]; p != NULL; p = p->next) {
  1369.         tri_normal (p->tri, new_norm);
  1370.         if (vect_angle (curr_norm, new_norm) < smooth_angle)
  1371.         vect_add (norm[i], norm[i], new_norm);
  1372.     }
  1373.  
  1374.     mag = vect_mag(norm[i]);
  1375.     if (mag > 0.0)
  1376.         vect_scale (norm[i], 1.0/mag);
  1377.     else
  1378.         vect_init (norm[i], 0.0, 0.0, 0.0);
  1379.     }
  1380. }
  1381.  
  1382.  
  1383. /* Calculates the normal to the specified triangle */
  1384. void tri_normal (Triangle *t, Vector normal)
  1385. {
  1386.     Vector ab, ac;
  1387.     float  mag;
  1388.  
  1389.     vect_subtr (ab, vtable[t->vert[1]], vtable[t->vert[0]]);
  1390.     vect_subtr (ac, vtable[t->vert[2]], vtable[t->vert[0]]);
  1391.     cross_prod (normal, ac, ab);
  1392.  
  1393.     mag = vect_mag (normal);
  1394.     if (mag > 0.0)
  1395.     vect_scale (normal, 1.0/mag);
  1396.     else
  1397.     vect_init (normal, 0.0, 0.0, 0.0);
  1398. }
  1399.  
  1400.  
  1401. /* Find the specified rgb values in the palette table */
  1402. unsigned pal_lookup (float red, float green, float blue)
  1403. {
  1404.     int i;
  1405.  
  1406.     /* The palette table is usually small so just do a simple linear search */
  1407.     for (i = psize-1; i >= 0; i--) {
  1408.     if (ptable[i].red   == red &&
  1409.         ptable[i].green == green &&
  1410.         ptable[i].blue  == blue)
  1411.       break;
  1412.     }
  1413.  
  1414.     if (i >= 0)
  1415.     return i;    /* found, return the table index */
  1416.  
  1417.     /* not found, insert the new palette into the table */
  1418.     ++psize;
  1419.     if (psize > pmax) {
  1420.     /* table not big enough, resize it */
  1421.     pmax = pmax + 10;
  1422.     ptable = realloc (ptable, pmax * sizeof(Palette));
  1423.     if (ptable == NULL)
  1424.         abortmsg ("Insufficient memory to expand palette table.", 1);
  1425.     }
  1426.  
  1427.     ptable[psize-1].red   = red;
  1428.     ptable[psize-1].green = green;
  1429.     ptable[psize-1].blue  = blue;
  1430.  
  1431.     return (psize-1);
  1432. }
  1433.  
  1434.  
  1435. /* Find the specified named texture in the texture table */
  1436. unsigned texture_lookup (char *texture_name)
  1437. {
  1438.     int i;
  1439.  
  1440.     /* The texture table is usually small so just do a simple linear search */
  1441.     for (i = tsize-1; i >= 0; i--) {
  1442.     if (strcmp (ttable[i], texture_name) == 0)
  1443.         break;
  1444.     }
  1445.  
  1446.     if (i >= 0)
  1447.     return i;    /* found, return the table index */
  1448.  
  1449.     /* not found, insert the new texture into the table */
  1450.     ++tsize;
  1451.     if (tsize > tmax) {
  1452.     /* table not big enough, resize it */
  1453.     tmax = tmax + 10;
  1454.     ttable = realloc (ttable, tmax * sizeof(Texture));
  1455.     if (ttable == NULL)
  1456.         abortmsg ("Insufficient memory to expand palette table.", 1);
  1457.     }
  1458.  
  1459.     ttable[tsize-1] = malloc (strlen(texture_name) + 1);
  1460.     if (ttable[tsize-1] == NULL)
  1461.     abortmsg ("Insufficient memory for texture name.", 1);
  1462.  
  1463.     strcpy (ttable[tsize-1], texture_name);
  1464.  
  1465.     return (tsize-1);
  1466. }
  1467.  
  1468.  
  1469. /* Find the specified vertex in the vertex table */
  1470. unsigned vert_lookup (float x, float y, float z)
  1471. {
  1472.     VertList *p, *new_node;
  1473.     unsigned hash;
  1474.  
  1475.     /* Vertex table is usually very large, use hash lookup */
  1476.     hash = (unsigned)((int)(326.4*x) ^ (int)(694.7*y) ^ (int)(1423.6*z)) % HASHSIZE;
  1477.  
  1478.     for (p = vert_hash[hash]; p != NULL; p = p->next) {
  1479.     if (vtable[p->vert][0] == x && vtable[p->vert][1] == y &&
  1480.         vtable[p->vert][2] == z) break;
  1481.     }
  1482.  
  1483.     if (p != NULL)
  1484.     return (p->vert);   /* found, return the table index */
  1485.  
  1486.     /* not found, insert the new vertex into the table */
  1487.     ++vsize;
  1488.     if (vsize > vmax) {
  1489.     /* table not big enough, expand it */
  1490.     vmax = vmax + 100;
  1491.     vtable = realloc (vtable, vmax * sizeof(Vector));
  1492.     if (vtable == NULL)
  1493.         abortmsg ("Insufficient memory for vertices.\n", 1);
  1494.     }
  1495.  
  1496.     vect_init (vtable[vsize-1], x, y, z);
  1497.  
  1498.     new_node = malloc (sizeof(VertList));
  1499.     if (new_node == NULL)
  1500.     abortmsg ("Insufficient memory for hash table.", 1);
  1501.  
  1502.     new_node->vert  = vsize-1;
  1503.     new_node->next  = vert_hash[hash];
  1504.     vert_hash[hash] = new_node;
  1505.  
  1506.     return (vsize-1);
  1507. }
  1508.  
  1509.  
  1510. void vect_init (Vector v, float x, float y, float z)
  1511. {
  1512.     v[0] = x;
  1513.     v[1] = y;
  1514.     v[2] = z;
  1515. }
  1516.  
  1517.  
  1518. void vect_copy (Vector v1, Vector v2)
  1519. {
  1520.     v1[0] = v2[0];
  1521.     v1[1] = v2[1];
  1522.     v1[2] = v2[2];
  1523. }
  1524.  
  1525.  
  1526. int vect_equal (Vector v1, Vector v2)
  1527. {
  1528.     if (v1[0] == v2[0] && v1[1] == v2[1] && v1[2] == v2[2])
  1529.     return 1;
  1530.     else
  1531.     return 0;
  1532. }
  1533.  
  1534.  
  1535. void vect_add (Vector v1, Vector v2, Vector v3)
  1536. {
  1537.     v1[0] = v2[0] + v3[0];
  1538.     v1[1] = v2[1] + v3[1];
  1539.     v1[2] = v2[2] + v3[2];
  1540. }
  1541.  
  1542.  
  1543. void vect_subtr (Vector v1, Vector v2, Vector v3)
  1544. {
  1545.     v1[0] = v2[0] - v3[0];
  1546.     v1[1] = v2[1] - v3[1];
  1547.     v1[2] = v2[2] - v3[2];
  1548. }
  1549.  
  1550.  
  1551. void vect_scale (Vector v, float k)
  1552. {
  1553.     v[0] = k * v[0];
  1554.     v[1] = k * v[1];
  1555.     v[2] = k * v[2];
  1556. }
  1557.  
  1558.  
  1559. float vect_mag (Vector v)
  1560. {
  1561.     float mag = sqrt(v[0]*v[0] + v[1]*v[1] + v[2]*v[2]);
  1562.  
  1563.     return mag;
  1564. }
  1565.  
  1566.  
  1567. float dot_prod (Vector v1, Vector v2)
  1568. {
  1569.     return (v1[0]*v2[0] + v1[1]*v2[1] + v1[2]*v2[2]);
  1570. }
  1571.  
  1572.  
  1573. void cross_prod (Vector v1, Vector v2, Vector v3)
  1574. {
  1575.     v1[0] = (v2[1] * v3[2]) - (v2[2] * v3[1]);
  1576.     v1[1] = (v2[2] * v3[0]) - (v2[0] * v3[2]);
  1577.     v1[2] = (v2[0] * v3[1]) - (v2[1] * v3[0]);
  1578. }
  1579.  
  1580.  
  1581. /* Return the angle between two vectors */
  1582. float vect_angle (Vector v1, Vector v2)
  1583. {
  1584.     float mag1, mag2, angle, cos_theta;
  1585.  
  1586.     mag1 = vect_mag(v1);
  1587.     mag2 = vect_mag(v2);
  1588.  
  1589.     if (mag1 * mag2 == 0.0)
  1590.     angle = 0.0;
  1591.     else {
  1592.     cos_theta = dot_prod(v1,v2) / (mag1 * mag2);
  1593.  
  1594.     if (cos_theta <= -1.0)
  1595.         angle = 180.0;
  1596.     else if (cos_theta >= +1.0)
  1597.         angle = 0.0;
  1598.     else
  1599.         angle = 180.0 * (acos(cos_theta) / PI);
  1600.     }
  1601.  
  1602.     return angle;
  1603. }
  1604.  
  1605.  
  1606. void vect_print (FILE *f, Vector v, int dec)
  1607. {
  1608.     char fstr[] = "<%.4f %.4f %.4f> ";
  1609.  
  1610.     if (dec < 0) dec = 0;
  1611.     if (dec > 9) dec = 9;
  1612.  
  1613.     fstr[3]  = '0' + dec;
  1614.     fstr[8]  = '0' + dec;
  1615.     fstr[13] = '0' + dec;
  1616.  
  1617.     fprintf (f, fstr, v[0], v[1], v[2]);
  1618. }
  1619.  
  1620.  
  1621. /* Checks if triangle is degenerate (zero area) */
  1622. int  degen_tri (float ax, float ay, float az,
  1623.         float bx, float by, float bz,
  1624.         float cx, float cy, float cz)
  1625. {
  1626.     Vector ab, ac, norm;
  1627.     float  mag, fact;
  1628.  
  1629.     fact = pow10 (dec_point);
  1630.  
  1631.     /* Round the coords off to the output precision before checking */
  1632.     ax = floor((ax*fact) + 0.5)/fact;
  1633.     ay = floor((ay*fact) + 0.5)/fact;
  1634.     az = floor((az*fact) + 0.5)/fact;
  1635.     bx = floor((bx*fact) + 0.5)/fact;
  1636.     by = floor((by*fact) + 0.5)/fact;
  1637.     bz = floor((bz*fact) + 0.5)/fact;
  1638.     cx = floor((cx*fact) + 0.5)/fact;
  1639.     cy = floor((cy*fact) + 0.5)/fact;
  1640.     cz = floor((cz*fact) + 0.5)/fact;
  1641.  
  1642.     vect_init (ab, ax-bx, ay-by, az-bz);
  1643.     vect_init (ac, ax-cx, ay-cy, az-cz);
  1644.     cross_prod (norm, ab, ac);
  1645.  
  1646.     mag = vect_mag(norm);
  1647.  
  1648.     return (mag < DEGEN_TOL);
  1649. }
  1650.  
  1651.  
  1652. void abortmsg (char *msg, int exit_code)
  1653. {
  1654.     printf ("\n%s\n", msg);
  1655.     exit (exit_code);
  1656. }
  1657.  
  1658.  
  1659. float fmin (float a, float b)
  1660. {
  1661.     if (a < b)
  1662.     return a;
  1663.     else
  1664.     return b;
  1665. }
  1666.  
  1667.  
  1668. float fmax (float a, float b)
  1669. {
  1670.     if (a > b)
  1671.     return a;
  1672.     else
  1673.     return b;
  1674. }
  1675.  
  1676.  
  1677. void add_ext (char *fname, char *ext, int force)
  1678. {
  1679.     int i;
  1680.  
  1681.     for (i = 0; i < strlen(fname); i++)
  1682.     if (fname[i] == '.') break;
  1683.  
  1684.     if (fname[i] == '\0' || force) {
  1685.     if (strlen(ext) > 0)
  1686.         fname[i++] = '.';
  1687.  
  1688.     strcpy (&fname[i], ext);
  1689.     }
  1690. }
  1691.  
  1692.  
  1693. void cleanup_name (char *name)
  1694. {
  1695.     char *tmp = malloc (strlen(name)+1);
  1696.     int  i;
  1697.  
  1698.     i = 0;
  1699.     while (name[i] == ' ' && name[i] != '\0')
  1700.     i++;
  1701.  
  1702.     strcpy (tmp, &name[i]);
  1703.  
  1704.     for (i = strlen(tmp)-1; i >= 0; i--) {
  1705.     if (isprint(tmp[i]) && !isspace(tmp[i]))
  1706.         break;
  1707.     else
  1708.         tmp[i] = '\0';
  1709.     }
  1710.  
  1711.     strcpy (name, tmp);
  1712.  
  1713.     /* Prepend an underscore to materials that begin with a digit */
  1714.     if (!isdigit (name[0]))
  1715.        strcpy (tmp, name);
  1716.     else {
  1717.        tmp[0] = '_';
  1718.        strcpy (&tmp[1], name);
  1719.     }
  1720.  
  1721.     /* Replace all illegal charaters in name with underscores */
  1722.     for (i = 0; tmp[i] != '\0'; i++) {
  1723.        if (!isalnum(tmp[i]))
  1724.        tmp[i] = '_';
  1725.     }
  1726.  
  1727.     strcpy (name, tmp);
  1728.  
  1729.     free (tmp);
  1730. }
  1731.  
  1732.  
  1733.